package com.asia.algorithmcode.binaryTree;

import java.util.HashMap;
import java.util.Map;

/**
 * @DESCRIPTION: 105、从前序遍历和中序遍历恢复二叉树
 * @USER: wanfu
 * @DATE: 2025/5/9 星期五 15:53
 */
public class BuildTree {

    public static void main(String[] args) {
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};

        TreeNode treeNode = new BuildTree().buildTree(preorder, inorder);

        System.out.println(treeNode);
    }

    Map<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int pl, int pr, int[] inorder, int il, int ir) {

        if (pl > pr) {
            return null;
        }

        int rootV = preorder[pl];
        Integer i = map.get(rootV);
        TreeNode root = new TreeNode(rootV);

        root.left = build(preorder, pl + 1, pl + 1 + i - 1 - il, inorder, il, i - 1);
        root.right = build(preorder, pl + 1 + i - 1 - il + 1, pr, inorder, i + 1, ir);

        return root;
    }
}
